package leetcode.backtrace;

/**
 * @Description
 * @Author 26233
 * @Create 2021-04-19 20:43:21
 */

/*

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
 

示例 1：


输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
示例 2：

输入：board = [["X"]]
输出：[["X"]]
 

提示：

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 'X' 或 'O'

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/surrounded-regions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 */

public class LeetCode130_Solve {
    public void solve(char[][] board) {

        int[][] visited = new int[board.length][board[0].length];
        int i = 0, j = 0;

        // 左
        for (;i < board.length; i++){
            if (board[i][j] == 'O') solve(board, i, j, visited);
        }
        // 上
        i = 0;
        for (;j < board[0].length; j++){
            if (board[i][j] == 'O') solve(board, i, j, visited);
        }
        // 下
        i = board.length - 1;
        j = 0;
        for (;j < board[0].length; j++){
            if (board[i][j] == 'O') solve(board, i, j, visited);
        }
        // 右
        i = 0;
        j = board[0].length - 1;
        for (;i < board.length; i++){
            if (board[i][j] == 'O') solve(board, i, j, visited);
        }

        for (i = 0; i < board.length; i++){
            for(j = 0; j < board[0].length; j++){
                if (board[i][j] == 'O' && visited[i][j] != 1){
                    board[i][j] = 'X';
                }
            }
        }

    }
    public void solve(char[][] board, int i, int j, int[][] visited) {
        if ((i >= 0 && i < board.length) && (j >=0 && j < board[0].length) && visited[i][j] != 1 && board[i][j] == 'O'){
            visited[i][j] = 1;
            solve(board, i - 1, j, visited);
            solve(board, i + 1, j, visited);
            solve(board, i, j - 1, visited);
            solve(board, i, j + 1, visited);
        }
    }

    public static void main(String[] args) {
        // char[][] board = {{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}};
        char[][] board = {{'X','O','X'},{'O','X','O'},{'X','O','X'}};
        new LeetCode130_Solve().solve(board);

        System.out.println("board = " + board);
    }
}
